package leetcode;

import java.util.*;


class ListNode {
    int val;
    ListNode next;

    ListNode() {}
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Demo5 {


    //2. 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        int carry = 0;

        while(l1 != null || l2 != null || carry > 0) {
            if(l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            ListNode node = new ListNode(carry % 10);
            tail.next = node;
            tail = tail.next;
            carry /= 10;
        }

        return newHead.next;
    }


    //24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode prev = newHead, cur = head, next = cur.next, nnext = next.next;
        while (cur != null && next != null) {
            prev.next = next;
            next.next = cur;
            cur.next = nnext;

            prev = cur;
            cur = nnext;
            if(cur == null || cur.next == null) break;
            next = cur.next;
            nnext = next.next;
        }
        return newHead.next;
    }



    //LCR 026. 重排链表
    public void reorderList(ListNode head) {
        if(head.next == null) return;

        // 1. 找到链表的中间结点, 即slow
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2. 翻转slow 后面结点的链表
        ListNode tmpHead = null;
        ListNode tmp = slow;
        while(slow != null) {
            ListNode next = slow.next;
            slow.next = tmpHead;
            tmpHead = slow;
            slow = next;
        }
        // 3. 按先后顺序将前后两个链表合并
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while(head != tmp ) {
            ListNode next1 = head.next, next2 = tmpHead.next;
            tail.next = head;
            head.next = tmpHead;

            tail = tmpHead;
            head = next1;
            tmpHead = next2;
        }
        head = newHead.next;
    }




    //LCR 078. 合并 K 个升序链表
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        return mergeSort(lists, 0, lists.length - 1);
    }

    private ListNode mergeSort(ListNode[] lists, int left, int right) {
        if(left >= right) return lists[left];

        // 1. 划分链表
        int mid = (left + right) / 2;
        ListNode head1 = mergeSort(lists, left, mid);
        ListNode head2 = mergeSort(lists, mid + 1, right);

        // 2. 合并 head1 和 head2
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while(head1 != null && head2 != null) {
            if(head1.val <= head2.val) {
                tail.next = head1;
                head1 = head1.next;
            } else {
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        if(head1 != null) tail.next = head1;
        if(head2 != null) tail.next = head2;

        return newHead.next;
    }





    //25. K 个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1 || head.next == null) return head;

        // 1. 统计需要翻转多个组链表
        int count = 0;
        ListNode cur = head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        count /= k;

        // 2. 进行 count 次翻转, 每次翻转 k 个结点
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        cur = head;
        for(int i = 0; i < count; i++) {
            ListNode tmpHead = null;
            ListNode tmp = cur;
            for(int j = 0; j < k; j++) {
                ListNode next = cur.next;
                cur.next = tmpHead;
                tmpHead = cur;
                cur = next;
            }
            tail.next = tmpHead;
            tail = tmp;
        }
        tail.next = cur;
        return newHead.next;
    }





    //1. 两数之和
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            if(hash.containsKey(x)) {
                return new int[]{i, hash.get(x)};
            }else {
                hash.put(nums[i], i);
            }
        }

        return null;
    }




    //面试题 01.02. 判定是否互为字符重排
    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()) return false;

        int[] hash = new int[26];
        for(int i = 0; i < s1.length(); i++) {
            char ch = s1.charAt(i);
            hash[ch-'a']++;
        }
        for(int i = 0; i < s2.length(); i++) {
            char ch = s2.charAt(i);
            if(--hash[ch - 'a'] < 0) return false;
        }
        return true;
    }



    //219. 存在重复元素 II
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> hash = new HashMap<>();

        for(int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if(hash.containsKey(x)) {
                if(i - hash.get(x) <= k) return true;
            }
            hash.put(x, i);
        }
        return false;
    }



    //LCR 033. 字母异位词分组
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();

        for(String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);

            if(!hash.containsKey(key)) {
                hash.put(key, new ArrayList<>());
            }
            hash.get(key).add(str);
        }

        return new ArrayList<>(hash.values());
    }




    //5. 最长回文子串
    public String longestPalindrome(String s) {
        int len = 0, begin = 0, end = 0;
        for(int i = 0; i < s.length(); i++) {
            int left = i, right = i;
            // 寻找奇数回文字符串
            for(; left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right); left--, right++);
            if(right - left - 1 > len) {
                begin = left + 1;
                end = right;
                len = right - left - 1;
            }
            // 寻找偶数回文字符串
            for(left = i,right = i + 1; left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right); left--,right++);
            if(right - left - 1 > len) {
                begin = left + 1;
                end = right;
                len = right - left - 1;
            }
        }
        return s.substring(begin, end);
    }



    //67. 二进制求和
    public String addBinary(String a, String b) {
        int carry = 0;
        StringBuffer ret = new StringBuffer();
        for(int cur1 = a.length() - 1, cur2 = b.length() - 1; cur1 >= 0 || cur2 >= 0 || carry > 0; cur1--,cur2--) {
            if(cur1 >= 0) carry += a.charAt(cur1) - '0';
            if(cur2 >= 0) carry += b.charAt(cur2) - '0';
            ret.insert(0, (char) ((carry % 2) + '0'));
            carry /= 2;
        }

        return ret.toString();
    }


    //43. 字符串相乘
    public String multiply(String num1, String num2) {
        num1 = new StringBuilder(num1).reverse().toString();
        num2 = new StringBuilder(num2).reverse().toString();
        int m = num1.length(), n = num2.length();
        int[] arr = new int[m + n - 1];

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                arr[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }

        int carry = 0;
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < arr.length || carry > 0; ) {
            if(i < arr.length) carry += arr[i++];
            ret.append((char) (carry % 10 + '0'));
            carry /= 10;
        }
        // 处理前导0
        while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') ret.deleteCharAt(ret.length() - 1);
        return ret.reverse().toString();
    }




    //844. 比较含退格的字符串
    public boolean backspaceCompare(String s, String t) {
        return changeStr(s).equals(changeStr(t));
    }
    public String changeStr(String s) {
        StringBuilder ret = new StringBuilder();
        for(char ch : s.toCharArray()) {
            if(ch != '#') {
                ret.append(ch);
            } else {
                if(ret.length() > 0) ret.deleteCharAt(ret.length() - 1);
            }
        }
        return ret.toString();
    }


    //227. 基本计算器 II
    public int calculate(String _s) {
        Deque<Integer> stack = new ArrayDeque<>();
        char op = '+';
        char[] s = _s.toCharArray();

        for(int i = 0; i < s.length; ) {
            if(s[i] == ' ') {
                i++;
            }else if(s[i] >= '0' && s[i] <= '9') {
                int tmp = 0;
                while(i < s.length && s[i] >= '0' && s[i] <= '9') {
                    tmp = tmp * 10 + (s[i++] - '0');
                }
                if(op == '-') tmp = -tmp;
                else if(op == '*') tmp *= stack.pop();
                else if(op == '/') tmp = stack.pop() / tmp;
                stack.push(tmp);
            } else {
                op = s[i++];
            }
        }

        int ret = 0;
        while(!stack.isEmpty()) ret += stack.pop();
        return ret;
    }



    //394. 字符串解码
    public String decodeString(String _s) {
        Deque<String> strSt = new ArrayDeque<>();
        Deque<Integer> intSt = new ArrayDeque<>();
        strSt.push("");
        char[] s = _s.toCharArray();
        int i = 0, n = s.length;

        while(i < n) {
            if(s[i] >= '0' && s[i] <= '9') {    // 遇到数字，提取数字放入数组栈
                int tmp = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9') {
                    tmp = tmp * 10 + (s[i++] - '0');
                }
                intSt.push(tmp);
            } else if(s[i] == '[') {            // 遇到 [ 括号，提取里面的字符串,入栈
                i++;
                StringBuilder tmp = new StringBuilder();
                while(i < n && s[i] >= 'a' && s[i] <= 'z') {
                    tmp.append(s[i++]);
                }
                strSt.push(tmp.toString());
            } else if(s[i] == ']') {            // 遇到 ] 括号，重复字符串，并拼接到栈顶元素的后面
                i++;
                StringBuilder tmp = new StringBuilder();
                String copy = strSt.pop();
                for(int count = intSt.pop(); count > 0; count--) {
                    tmp.append("" + copy);
                }
                strSt.push(strSt.pop() + tmp.toString());
            } else {                            // 遇到普通字符串，提取字符串，拼接到栈顶元素的后面
                StringBuilder tmp = new StringBuilder();
                while(i < n && s[i] >= 'a' && s[i] <= 'z') {
                    tmp.append(s[i++]);
                }
                strSt.push(strSt.pop() + tmp.toString());
            }
        }
        return strSt.pop();
    }



    //946. 验证栈序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> st = new ArrayDeque<>();
        int i = 0;
        for(int x : pushed) {
            st.push(x);
            while(!st.isEmpty() && popped[i] == st.peek()) {
                st.pop();
                i++;
            }
        }
        return st.size() == 0;
    }

}
